#coding=utf-8 
'''
Created on 2012-10-14

@author: infear
'''
import re
from random import random, randint
#http://blog.csdn.net/v_JULY_v/article/details/6234496
#google八道面试题 
#16、正整数序列Q中的每个元素都至少能被正整数a和b中的一个整除，现给定a和b，需要计算出Q中的前几项，例如，当a=3，b=5，N=6时，序列为3，5，6，9，10，12
#(1)、设计一个函数void generate（int a,int b,int N ,int * Q）计算Q的前几项
#(2)、设计测试数据来验证函数程序在各种输入下的正确性。
def generate(a,b,N):
    i=1;
    while N!=0:
        if i%a==0 or i%b==0:
            N=N-1
            yield i     
        i=i+1

#17、有一个由大小写组成的字符串，现在需要对他进行修改，将其中的所有小写字母排在答谢字母的前面（大写或小写字母之间不要求保持原来次序），
#如有可能尽量选择时间和空间效率高的算法 c语言函数原型void proc（char *str） 也可以采用你自己熟悉的语言
def proc(_str):
    low_re,upper_re='([a-z])+$','([A-Z])+$'
    _str=list(_str)
    _len=len(_str)
    i,j=0,_len-1
    while i<j:
        while j>=0 and re.match(upper_re,_str[j]):
            j=j-1
        while i<_len and re.match(low_re,_str[i]):
            i=i+1
        if i<j:
            _str[i],_str[j]=_str[j],_str[i]
        else:
            break;
    return str(_str)

#18、如何随机选取1000个关键字
#给定一个数据流，其中包含无穷尽的搜索关键字（比如，人们在谷歌搜索时不断输入的关键字）。如何才能从这个无穷尽的流中随机的选取1000个关键字？
#用数学归纳法证明：假设前 i个数每个数被取到的概率是k/i,那么对于第i+1个数，首先生成一个0到i的随机数，每一个数的概率为1/(i+1)
#如果这个数落在【0，N-1】之间，那么list上这个位置的数就被第i+1个数替换，这样的概率是1/(i+1)×(k/i)
#这样子，对于前i个数仍然存在于list中的概率就是k/i-k/i*1/(i+1)=k/(i+1),归纳完成 
def get_random_key(N,it):
    i=0
    _list=[]
    while i!=N:
        _list.append(it.next())
        i=i+1
    while it.hasNext():
        i=i+1
        index=random.randrange(0,i)
        if index<N:
            _list[index]=it.next()    
            
#19、判断一个自然数是否是某个数的平方
#说明：当然不能使用开方运算
def findSquare(start,end,n):
    print "findSquare",start,end
    if start==end:
        if start*start==n:
            return start
        return None
    else:
        mid=int((start+end)/2)
        if mid*mid==n:
            return mid
        elif mid*mid<n:
            return findSquare(mid+1,end,n)
        else:
            return findSquare(start,mid,n)
        
#20、给定能随机生成整数1到5的函数，写出能随机生成整数1到7的函数。
def generate_random(a):
    return randint(1,a)

def generate_random_from_seed(a,b):
    i=0
    while pow(a,i)-1<b:
        i=i+1
    j=i
    result=pow(a,i)
    while result%b!=0:
        result=result-1
    new_seed=0
    while True:
        while i!=0:
            new_seed=new_seed+generate_random(a)*pow(a,i-1)
            i=i-1
        if new_seed<=result:
            return new_seed%b+1 
        i,new_seed=j,0  
      
#21、1024! 末尾有多少个0？
def findZeroNum(N):
    num,base=0,5
    root=base
    while N/root>=1:
        num=num+N/root
        root=root*base
    return num

#23、Google2009华南地区笔试题
#给定一个集合A=[0,1,3,8](该集合中的元素都是在0，9之间的数字，但未必全部包含)，
#指定任意一个正整数K，请用A中的元素组成一个大于K的最小正整数。
#
#比如，A=[1,0] K=21 那么输出结构应该为100。
#这个题的思路是这样的：
#1.需要找出数组中最小的min,非0最小的not_zero_min,以及大于N最高位最小的over_min
#2.根据over_min的情况分类，（1）如果小于N的最高位，那么结果就是第一位是not_zero_min,之后的N位都是min。（2）如果大于N的最高位，那么结果就是最高位是over_min，之后的
#N-1位都是min。(3)如果等于N的最高位，令w=N-pow(10,len(N)-1)*over_min，对w进行递归得到结果r，如果r的位数与w相同，则返回w+r,否则的话，就说明不能得到最高位与N相同的最小结果，转入3
#3.遍历数组，观察是否有大于over_min的数larger_min，如果有，那么返回结果最高位为larger_min,之后的N-1位都是min，否则返回最高位为not_zero_min,之后的N位为min
#其实这个函数实现的是不小于N的情况
       
def func(_arr,N):
    high_bits=int(list(str(N))[0])
    _min,_not_zero_min,over_min=10,10,10
    _len=len(_arr)-1
    for j in _arr:
        if j<_min:
            _min=j
        if j!=0 and j<_not_zero_min:
            _not_zero_min=j
        if j<over_min and j>=high_bits:
            over_min=j
    if _not_zero_min==0:
        return None
    result=0
    if over_min==10:
        result=_not_zero_min*pow(10,len(str(N)))
        for k in range(0,len(str(N))):
            result=result+_min*pow(10,k)
        return result
    elif over_min>high_bits:
        result=over_min*pow(10,len(str(N))-1)
        for k in range(0,len(str(N))-1):
            result=result+_min*pow(10,k)
        return result
    else:
        w=over_min*pow(10,len(str(N))-1)
        temp=func(_arr,N-w)
        if len(list(str(temp)))==len(list(str(N-w))):
            #N-w=0表示比较已经完成
            if N-w!=0:
                result=temp+w
            else:
                result=w
            return result
        else:
            for j in _arr:
                if j<=over_min:
                    pass
                else:
                    break
            if j>over_min:
                result=j*pow(10,len(str(N))-1)
                for i in range(0,len(str(N))-1):
                    result=result+_min*pow(10,i)
                return result
            else:
                result=_not_zero_min*pow(10,len(str(N)))
                for i in range(0,len(str(N))):
                    result=result+_min*pow(10,i)
                return result

#计算多项式的值
def calPoly(_arr,N,x):
    if N==0:
        return _arr[0]
    else:
        _arr[N-1]=_arr[N]*x+_arr[N-1]
        return calPoly(_arr,N-1,x)

#google2012笔试大题目2
def findZeroPos(_arr):
    for i in range(0,len(_arr)):
        if _arr[i]==0:
            return i
    return -1

def swap(_arr,i,j):
    _arr[i],_arr[j]=_arr[j],_arr[i]
    
def sortUsingSwap(_arr):
    zero_pos=findZeroPos(_arr)
    for i in range(0,len(_arr)):
        while _arr[i]!=i:
            j=_arr[i]
            if j!=0 and _arr[j]!=0:
                swap(_arr,zero_pos,i)
                swap(_arr,i,j)
                swap(_arr,j,zero_pos)
            else:
                break;
    swap(_arr,0,zero_pos)

#38、顺时针打印矩阵
#题目：输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
#例如：如果输入如下矩阵：
#
#1              2              3              4
#5              6              7              8
#9              10             11             12
#13             14             15             16
#则依次打印出数字1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10。
#需要注意只有一行时，不能有重复输出
def printArray(arr,start_x,start_y,end_x,end_y):
    if start_x>end_x or start_y>end_y:
        return
    if start_x==end_x:
        for i in range(start_y,end_y+1):
            print arr[start_x][i]
    elif start_y==end_y:
        for i in range(start_x,end_x+1):
            print arr[i][start_y]
    else:
        for i in range(start_y,end_y):
            print arr[start_x][i]
        for i in range(start_x,end_x):
            print arr[i][end_y]
        for i in range(start_y,end_y):
            print arr[end_x][start_y+end_y-i]
        for i in range(start_x,end_x):
            print arr[start_x+end_x-i][start_y]
        printArray(arr,start_x+1,start_y+1,end_x-1,end_y-1)

        

#test16
#print list(generate(3,5,7))

#test17
#_str="abaCde"
#print proc(_str)

#test19
#try:
#    print findSquare(0,100,99)
#except:
#    print None

#test20
#for i in range(1,11):
#    print generate_random_from_seed(5,24)
    

#test21
#print findZeroNum(84)

#test22
#print func([7,1,3],173)

#print calPoly([1,2,3,4],3,2)

#test#google2012笔试大题目2
#_arr=[4,3,5,1,2,0]
#sortUsingSwap(_arr)
#print _arr

#test 38
_list=[[1,2,3,4],[5,6,7,8],[9,10,11,12]]
printArray(_list,0,0,2,3)